import java.util.*;

public class NFA_To_DFA {

    /**
     * 寻找指定状态名称在邻接矩阵中的位置下标
     * @param nfaMatrix
     * @param name
     * @return
     */
    public static int findIndexInMatrix(NFAMatrix nfaMatrix, int name){
        for(int i = 0; i < nfaMatrix.stateCount; i++){
            if(nfaMatrix.r_states.get(i) == name){
                return i;
            }
        }
        return -1;
    }

    /**
     * 求一个状态的空闭包
     * @param nfaMatrix
     * @param stateName
     * @return
     */
    public static List<Integer> findEClosure(NFAMatrix nfaMatrix, int stateName){
        List<Integer> result = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        stack.push(stateName);
        while(!stack.empty()){
            int c = stack.pop();
            result.add(c);
            int index = findIndexInMatrix(nfaMatrix,c);
            for(int i = 0; i < nfaMatrix.stateCount; i++){
                if(nfaMatrix.accessMatrix[index][i].toString().equals("#")){
                    boolean isIn = false;
                    //如果已经在result里面了，就不能入栈，不然会死循环
                    for(int j = 0; j < result.size(); j++){
                        if(result.get(j).equals(nfaMatrix.r_states.get(i))){
                            isIn = true;
                            break;
                        }
                    }
                    if(!isIn){
                        stack.push(nfaMatrix.r_states.get(i));
                    }
                }
            }
        }
        return result;
    }

    /**
     * 求一个状态经转换后的的空闭包
     * @param nfaMatrix
     * @param stateName
     * @param access
     * @return
     */
    public static List<Integer> findTransferResult(NFAMatrix nfaMatrix, int stateName, Character access){
        List<Integer> result = new ArrayList<>();
        int index = findIndexInMatrix(nfaMatrix,stateName);
        for(int i = 0; i < nfaMatrix.stateCount; i++){
            if(nfaMatrix.accessMatrix[index][i].toString().contains(access.toString())){
                //将result和邻接矩阵的第i个状态的空闭包合并，但是要去重
                result.addAll(findEClosure(nfaMatrix,nfaMatrix.r_states.get(i)));
                LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet<>(result);
                result = new ArrayList<>(linkedHashSet);
            }
        }
        return result;
    }

    /**
     * 邻接表转为邻接矩阵
     * @param nfaGraph
     * @return
     */
    public static NFAMatrix graph_To_Matrix(NFAGraph nfaGraph){
        NFAMatrix nfaMatrix = new NFAMatrix();
        //初始化邻接矩阵边数
        nfaMatrix.arcCount = 0;
        //初始化邻接矩阵节点数
        //把弧集涉及的所有状态全部加入allState，然后去重，去重后countState的大小就是状态数
        List<Integer> allState = new ArrayList<>();
        for(int i = 0; i < nfaGraph.arcCount; i++){
            allState.add(nfaGraph.arcCollection[i].r_start);
            allState.add(nfaGraph.arcCollection[i].r_end);
        }
        LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet<>(allState);
        allState = new ArrayList<>(linkedHashSet);
        nfaMatrix.stateCount = allState.size();
        //初始化邻接矩阵顶点表
        nfaMatrix.r_states = new ArrayList<Integer>();
        for(int i = 0; i < nfaMatrix.stateCount; i++){
            nfaMatrix.r_states.add(allState.get(i));
        }
        //初始化邻接矩阵的边表，用^表示没有边
        nfaMatrix.accessMatrix = new StringBuffer[nfaMatrix.stateCount][nfaMatrix.stateCount];
        for(int i = 0; i < nfaMatrix.stateCount; i++){
            for(int j = 0; j < nfaMatrix.stateCount; j++){
                nfaMatrix.accessMatrix[i][j] = new StringBuffer();
            }
        }
        for(int i = 0; i < nfaMatrix.stateCount; i++){
            for(int j = 0; j < nfaMatrix.stateCount; j++){
                nfaMatrix.accessMatrix[i][j].append("^");
            }
        }
        //初始化开始状态
        nfaMatrix.r_startState = nfaGraph.r_StartState;
        //初始化结束状态集
        nfaMatrix.r_endStateList = nfaGraph.r_endStateList;
        //初始化转换条件集
        LinkedHashSet<Character> linkedHashSet1 = new LinkedHashSet<>(nfaGraph.access);
        nfaGraph.access = new ArrayList<>(linkedHashSet1);
        nfaMatrix.access = nfaGraph.access;
        //填充邻接矩阵的边表
        for(int i = 0; i < nfaGraph.arcCount; i++){
            int startIndex = findIndexInMatrix(nfaMatrix,nfaGraph.arcCollection[i].r_start);
            int endIndex = findIndexInMatrix(nfaMatrix,nfaGraph.arcCollection[i].r_end);
            if(startIndex != -1 && endIndex != -1){
                if(nfaMatrix.accessMatrix[startIndex][endIndex].toString().equals("^")){
                    nfaMatrix.accessMatrix[startIndex][endIndex].delete(0,1);
                }
                nfaMatrix.accessMatrix[startIndex][endIndex].append(nfaGraph.arcCollection[i].access);
                nfaMatrix.arcCount++;
            }else {
                System.out.println("邻接表中的状态在邻接矩阵中找不到");
                return null;
            }
        }
        return nfaMatrix;
    }

    /**
     * 邻接矩阵转为邻接表
     * @param nfaMatrix
     * @return
     */
    //邻接矩阵转为邻接表
    public static NFAGraph matrix_To_Graph(NFAMatrix nfaMatrix){
        NFAGraph nfaGraph = new NFAGraph();
        //初始化邻接表边数
        nfaGraph.arcCount = 0;
        //初始化开始状态
        nfaGraph.r_StartState = nfaMatrix.r_startState;
        //初始化结束状态集
        nfaGraph.r_endStateList = nfaMatrix.r_endStateList;
        //初始化转换条件集
        nfaGraph.access = nfaMatrix.access;
        nfaGraph.arcCollection = new Arc[100];
        //构建邻接表
        for(int i = 0; i < nfaMatrix.stateCount; i++){
            for(int j = 0; j < nfaMatrix.stateCount; j++){
                if(!nfaMatrix.accessMatrix[i][j].toString().equals("^")){
                    for(int k = 0; k < nfaMatrix.accessMatrix[i][j].length(); k++){
                        Arc newArc = new Arc();
                        newArc.r_start = nfaMatrix.r_states.get(i);
                        newArc.r_end = nfaMatrix.r_states.get(j);
                        newArc.access = nfaMatrix.accessMatrix[i][j].charAt(k);
                        nfaGraph.arcCollection[nfaGraph.arcCount] = newArc;
                        nfaGraph.arcCount++;
                    }
                }
            }
        }
        return nfaGraph;
    }

    /**
     * NFA邻接矩阵转为DFA邻接矩阵
     * @param nfaMatrix
     * @return
     */
    public static NFAMatrix NFAMatrix_To_DFAMatrix(NFAMatrix nfaMatrix){
        NFAMatrix dfaMatrix = new NFAMatrix();
        //定义一个list，存放新生成的DFA的各个状态（不可以有重复），每个状态包含了原来NFA的若干的状态
        List<List<Integer>> dfaStateList = new ArrayList<>();
        //定义一个辅助队列
        Queue<List<Integer>> queue = new LinkedList<>();
        //把开始状态的空闭包放入
        dfaStateList.add(findEClosure(nfaMatrix,nfaMatrix.r_startState));
        queue.offer(findEClosure(nfaMatrix,nfaMatrix.r_startState));
        //定义一个队列，保存所有DFA的边指向的状态，可以有重复，本质目的其实是存所有边，包括空边，最后大小会等于DFA状态数乘以转换条件数
        Queue<List<Integer>> dfaArcTo = new LinkedList<>();
        //获取DFA的状态，循环结束后queue为空，dfaStateList里放了DFA的所有状态和一个只有'^'的list
        while (!queue.isEmpty()){
            //让队首出队
            List<Integer> top = queue.poll();
            //遍历NFA的转换条件集
            for(int i = 0; i < nfaMatrix.access.size(); i++){
                char theAccess = nfaMatrix.access.get(i);
                //不要经过空的
                if(theAccess == '#'){
                    continue;
                }
                List<Integer> transferResultList = new ArrayList<>();
                //遍历队首的每一个原NFA的状态，求它经过转换条件后得到的空闭包，加入transferResultList，要去重
                for(int j = 0; j < top.size(); j++){
                    transferResultList.addAll(findTransferResult(nfaMatrix,top.get(j),theAccess));
                    LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet<>(transferResultList);
                    transferResultList = new ArrayList<>(linkedHashSet);
                }
                //如果transferResultList为空，说明队首的各个原NFA的状态不能经过这一轮循环的转换条件去下一个状态
                if(transferResultList.size() == 0){
                    transferResultList.add(-1);
                }
                //否则，看看这个状态是不是已经被加入过了，当没有被加入过时，才加入
                else {
                    boolean isIn = false;
                    //判断transferResultList这个状态和dfaStateList里面的各个状态是否相等
                    for(int j = 0; j < dfaStateList.size(); j++){
                        //大小不相等则肯定不相等
                        if(transferResultList.size() != dfaStateList.get(j).size()){
                            continue;
                        }
                        //大小相等时，把两个list都加入一个tempList，去重后如果大小和transferResultList一样，则相等
                        List<Integer> tempList = new ArrayList<>();
                        tempList.addAll(transferResultList);
                        tempList.addAll(dfaStateList.get(j));
                        LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet<>(tempList);
                        tempList = new ArrayList<>(linkedHashSet);
                        if(tempList.size() == transferResultList.size()){
                            isIn = true;
                        }
                    }
                    //如果transferResultList不在里面，就加入
                    if(!isIn){
                        dfaStateList.add(transferResultList);
                        queue.offer(transferResultList);
                    }
                }
                //无论transferResultList在不在dfaStateList中，都加入dfaArcTo，代表有这么一条弧（即使指向空）
                dfaArcTo.offer(transferResultList);
            }
        }
        //以下开始构造DFA
        //初始化DFAMatrix顶点数，即状态数
        dfaMatrix.stateCount = dfaStateList.size();
        //初始化DFAMatrix边数，其实就是NFA的状态数乘以转换条件的个数，不包括空边
        dfaMatrix.arcCount = dfaArcTo.size();
        //初始化DFAMatrix转换条件集
        dfaMatrix.access = nfaMatrix.access;
        //初始化dfaMatrix的顶点表，注意这里DFA的各顶点的名字是新取的
        dfaMatrix.r_states = new ArrayList<>();
        for(int i = 0; i < dfaMatrix.stateCount; i++){
            dfaMatrix.r_states.add(0);
        }
        for(int i = 0; i < dfaMatrix.stateCount; i++){
            dfaMatrix.r_states.set(i,i+1);
        }
        //初始化dfaMatrix的边表，用^表示没有边
        dfaMatrix.accessMatrix = new StringBuffer[dfaMatrix.stateCount][dfaMatrix.stateCount];
        for(int i = 0; i < dfaMatrix.stateCount; i++){
            for(int j = 0; j < dfaMatrix.stateCount; j++){
                dfaMatrix.accessMatrix[i][j] = new StringBuffer();
            }
        }
        for(int i = 0; i < dfaMatrix.stateCount; i++){
            for(int j = 0; j < dfaMatrix.stateCount; j++){
                dfaMatrix.accessMatrix[i][j].append("^");
            }
        }
        //填充dfaMatrix的边表
        int i = 0;
        while (!dfaArcTo.isEmpty()){
            //遍历DFA的转换条件集
            for(int j = 0; j < dfaMatrix.access.size(); j++){
                //不要经过空
                if(dfaMatrix.access.get(j) == '#'){
                    continue;
                }
                //队首出队
                List<Integer> theDfaArc = dfaArcTo.poll();
                //如果这条弧是空的，就什么也不做
                if(theDfaArc.size() == 1 && theDfaArc.get(0) == -1){
                }
                else {
                    //从DFA的各个状态中找到这条弧指向的状态，此时应该用没有重命名的，即由原NFA状态构成的DFA状态
                    int k;
                    for(k = 0; k < dfaStateList.size(); k++){
                        //大小不相等则肯定不相等
                        if(theDfaArc.size() != dfaStateList.get(k).size()){
                            continue;
                        }
                        //大小相等时，把两个list都加入一个tempList，去重后如果大小和theDfaArc一样，则相等
                        List<Integer> tempList = new ArrayList<>();
                        tempList.addAll(theDfaArc);
                        tempList.addAll(dfaStateList.get(k));
                        LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet<>(tempList);
                        tempList = new ArrayList<>(linkedHashSet);
                        if(tempList.size() == theDfaArc.size()){
                            break;
                        }
                    }
                    if(dfaMatrix.accessMatrix[i][k].toString().equals("^")){
                        dfaMatrix.accessMatrix[i][k].delete(0,1);
                    }
                    dfaMatrix.accessMatrix[i][k].append(dfaMatrix.access.get(j));
                }
            }
            i++;
        }
        //设置开始状态
        dfaMatrix.r_startState = dfaMatrix.r_states.get(0);
        //设置结束状态集
        dfaMatrix.r_endStateList = new ArrayList<>();
        for(int j = 0; j < dfaStateList.size(); j++){
            int index = dfaStateList.get(j).indexOf(nfaMatrix.r_endStateList.get(0));
            //如果DFA状态中能找的NFA的结束状态，则把这个DFA状态加入结束状态集，注意这里DFA状态命名要用初始化时命的新名字
            if(index != -1){
                dfaMatrix.r_endStateList.add(dfaMatrix.r_states.get(j));
            }
        }
        return dfaMatrix;
    }

    /**
     * NFA邻接表转为DFA邻接表
     * @param nfaGraph
     * @return
     */
    public static DFAGraph NFAGraph_To_DFAGraph(NFAGraph nfaGraph){
        //先把NFA的邻接表转为邻接矩阵
        NFAMatrix nfaMatrix = graph_To_Matrix(nfaGraph);
        //再转为DFA邻接矩阵
        NFAMatrix dfaMatrix = NFAMatrix_To_DFAMatrix(nfaMatrix);
        //再转为DFA邻接表
        NFAGraph dFAGraph = matrix_To_Graph(dfaMatrix);
        DFAGraph realDfaGraph = new DFAGraph(dFAGraph);
        //打印输出结果
        System.out.println("------------------------------------以下是转换后的DFA--------------------------------------");
        printGraph(realDfaGraph);
        System.out.println();
        return realDfaGraph;
    }

    /**
     * NFA邻接表转为DFA邻接矩阵
     * @param nfaGraph
     * @return
     */
    public static NFAMatrix NFAGraph_To_DFAMatrix(NFAGraph nfaGraph){
        //先把NFA的邻接表转为邻接矩阵
        NFAMatrix nfaMatrix = graph_To_Matrix(nfaGraph);
        //再转为DFA
        NFAMatrix dfaMatrix = NFAMatrix_To_DFAMatrix(nfaMatrix);
        return dfaMatrix;
    }

    /**
     * 打印邻接矩阵
     * @return
     */
    public static void printMatrix(NFAMatrix nfaMatrix){
        //打印顶点数
        System.out.println("顶点数：" + nfaMatrix.stateCount);
        //打印顶点集
        System.out.print("顶点集：");
        for(int i = 0; i < nfaMatrix.r_states.size(); i++){
            System.out.print(nfaMatrix.r_states.get(i) + " ");
        }
        System.out.println();
        //打印边数
        System.out.println("边数：" + nfaMatrix.arcCount);
        //打印边集
        System.out.println("边集：");
        for(int i = 0; i < nfaMatrix.accessMatrix.length; i++){
            for(int j = 0; j < nfaMatrix.accessMatrix[i].length; j++){
                System.out.print(nfaMatrix.accessMatrix[i][j].toString() + "\t");
            }
            System.out.println();
        }
        //打印转换条件集
        System.out.print("转换条件集：");
        for(int i = 0; i < nfaMatrix.access.size(); i++){
            System.out.print(nfaMatrix.access.get(i) + " ");
        }
        System.out.println();
        //打印开始状态
        System.out.println("开始状态：" + nfaMatrix.r_startState);
        //打印结束状态集
        System.out.print("结束状态：");
        for(int i = 0; i < nfaMatrix.r_endStateList.size(); i++){
            System.out.print(nfaMatrix.r_endStateList.get(i) + " ");
        }
        System.out.println();
    }

    /**
     * 打印邻接表
     * @return
     */
    public static void printGraph(NFAGraph nfaGraph){
        //打印边集
        System.out.println("边集：");
        for(int i = 0; i < nfaGraph.arcCount; i++){
            System.out.println(nfaGraph.arcCollection[i].r_start+"通过"+nfaGraph.arcCollection[i].access+"到"+nfaGraph.arcCollection[i].r_end);
        }
        //打印边数
        System.out.println("边数：" + nfaGraph.arcCount);
        //打印转换条件集
        System.out.print("转换条件集：");
        for(int i = 0; i < nfaGraph.access.size(); i++){
            System.out.print(nfaGraph.access.get(i) + " ");
        }
        System.out.println();
        //打印开始状态
        System.out.println("开始状态：" + nfaGraph.r_StartState);
        //打印结束状态集
        System.out.print("结束状态：");
        for(int i = 0; i < nfaGraph.r_endStateList.size(); i++){
            System.out.print(nfaGraph.r_endStateList.get(i) + " ");
        }
        System.out.println();
    }
}
